package Z.dailyExercise.May;

public class _477汉明距离总和 {

    /**
     * 暴力解==超时
     * @param nums
     * @return
     */
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                res += calculate(nums[i],nums[j]);

            }

        }
        return res;


    }
    public int calculate(int x,int y){
        int num = x ^ y;
        int res = 0;
        while (num != 0){
            num &= (num-1);
            res++;
        }
        return res;

    }

    /**
     * 题解：分类的思想 将所有元素纵向分析第i位  根据该位是0 还是1 对其统计数目 那么不同的个数总共就是 数目相乘
     * @param nums
     * @return
     */

    public int totalHammingDistance1(int[] nums) {
        int res  = 0;

        //i就是移位的循环
        for (int i = 31; i >= 0 ; i--) {
            int num_1 = 0;
            int num_0 = 0;

            for (int num :nums) {
                if (((num >> i) & 1 )== 1){
                    num_1++;
                }else {
                    num_0++;
                }

            }
            res += num_0*num_1;

        }

        return res;

    }
}
